package 剑指Offer;

public class Offer24_反转链表 {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;//指向反转后的节点的前节点
        ListNode cur = head;//指向即将反转的节点
        ListNode tmp = head;//保存即将要修改节点的下一个节点


        while (cur != null) {
            tmp = cur.next;
            //逐个节点反转
            cur.next = pre;
            //更新指针
            pre = cur;
            cur = tmp;
        }
        //cur 走到null了，那么pre在cur前一位，也就是新链表的头节点
        return pre;
    }

//    递归算法空间复杂度是o(N),所以选择迭代解法
//    public ListNode reverseList(ListNode head) {
//        if (head == null || head.next == null) {
//            return head;
//        }
//        ListNode last = reverseList(head.next);
//        head.next.next = head;
//        head.next = null;
//        return last;
//    }
}
